package uestc.lj.basic.sort;

import java.util.Arrays;

/**
 * 快排思想解决荷兰国旗问题
 *
 * @Author:Crazlee
 * @Date:2021/11/21
 */
public class Code01_quickSort {
    public static void quickSort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }

    /**
     * 使数组从left到right排好序
     *
     * @param array 待排序数组
     * @param left  左边界
     * @param right 右边界
     */
    public static void quickSort(int[] array, int left, int right) {
        if (left < right) {
            //随机选择一个位置和数组最右边数交换
            swap(array, left + (int) (Math.random() * (right - left + 1)), right);
            //返回的数组代表 等于上述随机选择数的左右边界
            int[] p = partition(array, left, right);
            quickSort(array, left, p[0] - 1);
            quickSort(array, p[1] + 1, right);
        }
    }

    /**
     * 分层函数，处理数组排序
     * 以数组最后一个元素为分界值进行左右两边排序，返回等于最后一个元素的左右边界
     *
     * @param array 待分数组
     * @param left  数组左边界
     * @param right 数组右边界
     * @return 等于数组最后一个元素的左右边界
     */
    private static int[] partition(int[] array, int left, int right) {
        //小于区域左边界
        int low = left - 1;
        //大于区域右边界
        int high = right;
        while (left < high) {
            //当前数比分界值小，将其于小于区域后一个元素交换，并将小于区域扩充一个位置，当前位置加一
            if (array[left] < array[right]) {
                swap(array, ++low, left++);
            } else if (array[left] > array[right]) {
                //当前数比分界值大，将其于大于区域前一个元素交换，并将大于区域后移一个位置，当前位置不变
                swap(array, --high, left);
            } else {
                //当前数和分界值相等，直接后移
                left++;
            }
        }
        //除最后一个元素外，其余都已排好，将最后一个元素排到其相对应的位置
        swap(array, high, right);
        return new int[]{low + 1, high};
    }

    private static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    public static void main(String[] args) {
        int[] array = {5, 7, 8, 2, 6, 1, 9, 3, 4};
        System.out.println("快排序之前数组元素为：");
        Arrays.stream(array).forEach(value -> System.out.print(value + " "));
        quickSort(array);
        System.out.println();
        System.out.println("快排序之后数组的元素为：");
        Arrays.stream(array).forEach(value -> System.out.print(value + " "));
    }
}
